#include "skiplist.h"
#include <QString>
#include <QVector>

Skiplist::Skiplist()
{

}

Skiplist::Skiplist(QVector<dataType> v)
{
    for(int i=0; i < v.size(); i++) {
	this->insertElem(v[i]);
    }
}

Cell *Skiplist::searchElem(dataType elem_to_find)
{
	Cell *found = this->getNext(0);

	for(int i = (this->getSize() - 1); i>=0; i--) {
		while(found->getNext(i) != NULL &&
				elem_to_find > found->getNext(i)->get()) {
			found = found->getNext(i);
		}
	}

	return found->getNext(0);
}

int Skiplist::insertElem(const dataType elem_to_insert)
{
	Cell *newone = new Cell;
	newone->set(elem_to_insert);

	Cell *here = this->getNext(0);
	QVector<Cell *> pointers(this->getSize());

	for (int i = this->getSize(); i >= 0; i--) {
		while(here->getNext(i) != NULL
		      && elem_to_insert > (here->getNext(i))->get()) {
			here = here->getNext(i);
		}
		pointers[i] = here;
	}

	if( here->getNext(0) != NULL && (here->getNext(0))->get() == elem_to_insert )
		return 1;

	else {
		int h;
		if(newone->getHeight() > this->getSize()) {
			newone->setHeight(this->getSize());
			pointers[newone->getHeight()-1] = newone;
		}

		h = newone->getHeight();

		while (--h >=0) {
			newone->setNext(h, pointers[h]);
		}
		return 0;
	}
	return -1;
}

int Skiplist::deleteElem(const dataType elem_to_delete)
{
    	Cell *here = getNext(0);
	Cell *safe;
	QVector<Cell *> pointers(getSize());

	for (int i = getSize(); i>=0; i--) {
		while (here->getNext(0) != NULL
		       && elem_to_delete > here->getNext(i)->get())
			here = here->getNext(i);
		pointers[i] = here;
	}

	if((here->getNext(0)==NULL)
	    || (here->getNext(0)->get()!=elem_to_delete))
		return -1;
	else{
		safe = pointers[0]->getNext(0);

		for (int i = 0; i < getSize(); i++) {
			if(pointers[i]->getNext(i) != NULL)
				pointers[i]->setNext(i,
				    pointers[i]->getNext(i)->getNext(i));
		}
		while (getSize() > 0) {
			if(getNext(0)->getNext(getSize()-1) != NULL)
				break;
			decrSize();
			getNext(0)->setNext(getSize(), NULL);
		}
	}
	delete safe;
	return 0;

}

int Skiplist::getSize(void)
{
	return this->height;
}

void Skiplist::setSize(int newSize)
{
	if(newSize >= 1)
		this->height = newSize;
	else
		this->height = 1;
}

void Skiplist::incrSize()
{
	this->height = this->getSize() + 1;
}

void Skiplist::decrSize()
{
	if(this->getSize() < 2)
		this->height = this->getSize() - 1;
}
